/**
 * 
 */
package array;

/**
 * @author Michael
 * Question: You are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.
 * Fastest way to find that single integer
 * eg:
 * Input: [2,1,4,5,1,4,2,2,4,1]
 * Answer: 5
 */
public class FindingUniqueNumber {

	public static int find(int[] arr) {
		assert (arr != null && arr.length >= 4);
		
		int ones = 0;
		int twos = 0;
		int notThree = 0;
		
		for (int i = 0; i < arr.length; ++i) {
			int n = arr[i];
			twos = twos | (ones & n);
			ones = ones ^ n;
			notThree = ~(ones & twos);
			ones = ones & notThree;
			twos = twos & notThree;
		}
		
		return ones;
	}
	
	/**
	 * 
	 */
	public FindingUniqueNumber() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//int[] arr = {1,1,1,3,3,3,20,4,4,4}; 
		int[] arr = { 6, 4, 6, 4, 5, 6, 4 };
		System.out.printf("%d\n", find(arr));
	}
}
